package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.List;

public class Code06_Subsets {
	public static List<List<Integer>> subsets(List<Integer> nums) {
		int nl = nums.size();
		// base case，返回一个空集
		if (nums == null || nl == 0) {
			List<List<Integer>> res = new ArrayList<List<Integer>>();
			return res;
		}
		// 把最后一个元素拿出来
		int n = nums.get(nl - 1);
		nums.remove(nl - 1);
		// 先递归算出前面元素的所有子集
		List<List<Integer>> res = subsets(nums);

		int size = res.size();
		for (int i = 0; i < size; i++) {
			// 然后在之前的结果之上追加
			res.add(res.get(i));
			res.get(i).add(n);
		}
		return res;
	}

	public static void printArray(List<List<Integer>> vec) {
		if (vec == null) {
			return;
		}
		for (int i = 0; i < vec.size(); i++) {
			System.out.print(vec.get(i) + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		{
			List<Integer> cur = new ArrayList<>();
			cur.add(1);
			cur.add(2);
			cur.add(3);

			List<List<Integer>> res = subsets(cur);
			printArray(res);
		}
		System.out.println("===========");
//		{
//			List<Integer> cur = new ArrayList<>();
//			int sums[] = { 2, 3, 5 };
//			int target = 8;
//			combinationSum02(cur, sums, target, 0);
//		}
	}
}
